package com.leetcode.algorithm.y22.m07.w4;

/**
 * 169. 多数元素
 * 
 * https://leetcode.cn/problems/majority-element/
 * 
 * @author jie.deng
 *
 */
class Question0169Solution01 {
	
	public int majorityElement(int[] nums) {
		// 摩尔投票法
		int target = nums[0];
		int cnt = 1;
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] == target) {
				cnt++;
			} else {
				if (cnt == 0) {
					target = nums[i];
					cnt = 1;
				} else {
					cnt--;
				}
			}
		}
		return target;
	}
    
}